home *** CD-ROM | disk | FTP | other *** search
/ Windows Expert / Windows Expert.iso / windownt / greps.zip / README < prev    next >
Text File  |  1993-09-17  |  3KB  |  71 lines
  1. This README documents GNU e?grep version 1.6.  All bugs reported for
  2. previous versions have been fixed.
  3.  
  4. See the file INSTALL for compilation and installation instructions.
  5.  
  6. Send bug reports to bug-gnu-utils@prep.ai.mit.edu.
  7.  
  8. GNU e?grep is provided "as is" with no warranty.  The exact terms
  9. under which you may use and (re)distribute this program are detailed
  10. in the GNU General Public License, in the file COPYING.
  11.  
  12. GNU e?grep is based on a fast lazy-state deterministic matcher (about
  13. twice as fast as stock Unix egrep) hybridized with a Boyer-Moore-Gosper
  14. search for a fixed string that eliminates impossible text from being
  15. considered by the full regexp matcher without necessarily having to
  16. look at every character.  The result is typically many times faster
  17. than Unix grep or egrep.  (Regular expressions containing backreferencing
  18. may run more slowly, however.)
  19.  
  20. GNU e?grep is brought to you by the efforts of several people:
  21.  
  22.     Mike Haertel wrote the deterministic regexp code and the bulk
  23.     of the program.
  24.  
  25.     James A. Woods is responsible for the hybridized search strategy
  26.     of using Boyer-Moore-Gosper fixed-string search as a filter
  27.     before calling the general regexp matcher.
  28.  
  29.     Arthur David Olson contributed code that finds fixed strings for
  30.     the aforementioned BMG search for a large class of regexps.
  31.  
  32.     Richard Stallman wrote the backtracking regexp matcher that is
  33.     used for \<digit> backreferences, as well as the getopt that
  34.     is provided for 4.2BSD sites.  The backtracking matcher was
  35.     originally written for GNU Emacs.
  36.  
  37.     D. A. Gwyn wrote the C alloca emulation that is provided so
  38.     System V machines can run this program.  (Alloca is used only
  39.     by RMS' backtracking matcher, and then only rarely, so there
  40.     is no loss if your machine doesn't have a "real" alloca.)
  41.  
  42.     Scott Anderson and Henry Spencer designed the regression tests
  43.     used in the "regress" script.
  44.  
  45.     Paul Placeway wrote the manual page, based on this README.
  46.  
  47. If you are interested in improving this program, you may wish to try
  48. any of the following:
  49.  
  50. 1.  Replace the fast search loop with a faster search loop.
  51.     There are several things that could be improved, the most notable
  52.     of which would be to calculate a minimal delta2 to use.
  53.  
  54. 2.  Make backreferencing \<digit> faster.  Right now, backreferencing is
  55.     handled by calling the Emacs backtracking matcher to verify the partial
  56.     match.  This is slow; if the DFA routines could handle backreferencing
  57.     themselves a speedup on the order of three to four times might occur
  58.     in those cases where the backtracking matcher is called to verify nearly
  59.     every line.  Also, some portability problems due to the inclusion of the
  60.     emacs matcher would be solved because it could then be eliminated.
  61.     Note that expressions with backreferencing are not true regular
  62.     expressions, and thus are not equivalent to any DFA.  So this is hard.
  63.  
  64. 3.  Handle POSIX style regexps.  I'm not sure if this could be called an
  65.     improvement; some of the things on regexps in the POSIX draft I have
  66.     seen are pretty sickening.  But it would be useful in the interests of
  67.     conforming to the standard.
  68.  
  69. 4.  Replace the main driver program grep.c with the much cleaner main driver
  70.     program used in GNU fgrep.
  71.